class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        // f(i) = max(i+nums[i], f(i-1))
        // i 表示下标，f(i) 表示能跳到的最远距离
        int[] numsNew = new int[nums.length + 1];
        System.arraycopy(nums, 0, numsNew, 1, nums.length);
        numsNew[0] = 1;
        int[] distance = new int[numsNew.length];
        distance[0] = 1;
        for (int i = 1; i < numsNew.length; i++) {
            distance[i] = Math.max(i + numsNew[i], distance[i - 1]);
            if (distance[i] <= i) {
                // 无法到达下一个数
                return false;
            } else if (distance[i] >= nums.length) {
                // 可以直接跳到终点
                return true;
            }
        }
        return false;
    }
}
